/*
============================================================================
Name        : dd_avl.h
Author      : Jian (raphyer@hotmail.com)
Version     :
Copyright   : GPL
Description : dd_avl.h - header file
============================================================================
*/

#ifndef DD_AVL_H
#define DD_AVL_H

#include "dd_define.h"

__DD_BEGIN_DECLS


/* 
* The AVL Tree (binary balance tree) Implement 
*/

typedef void                    dd_avl_key ;
typedef void                    dd_avl_value ;
typedef struct __dd_avl_node    dd_avl_node ;
typedef struct __dd_avl_tree    dd_avl_tree ;


struct __dd_avl_node {

    dd_avl_key*	    key ;
    dd_avl_value*   value ;
    dd_avl_node*    left_child ;
    dd_avl_node*    right_child ;
    DD_INT          height ;
};


struct __dd_avl_tree {
    dd_avl_node*	root ;
    DD_INT (*key_compare)(const dd_avl_key* key1, const dd_avl_key* key2) ;	/* 0: equal ; -1: key1 < key2 ; 1: key1 > key2 */
    void (*key_conflict)(dd_avl_key* key_found_conflict, dd_avl_value* value_found_conflict, dd_avl_key* key_handle, dd_avl_value* value_handle) ;
};


dd_avl_tree* dd_avl_create(
    DD_INT (*key_compare)(const dd_avl_key*, const dd_avl_key*), 
    void (*key_conflict)(dd_avl_key* , dd_avl_value*, dd_avl_key*, dd_avl_value*) 
) ;

void dd_avl_destroy(dd_avl_tree* avl) ;

dd_avl_value*  dd_avl_find(const dd_avl_tree* avl, dd_avl_key* key) ; 

void dd_avl_insert(dd_avl_tree* avl, dd_avl_key* key, dd_avl_value* value) ;

dd_avl_value* dd_avl_remove(dd_avl_tree* avl, dd_avl_key* key) ;


#ifdef __DD_UNITTEST

DD_BOOL dd_avl_test() ;

#endif


__DD_END_DECLS

#endif	/* DD_AVL_H */

/* End of File */
